package 链表;

import java.util.Stack;

//https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&tqId=1008772&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
public class BM11_链表相加二 {

	public static void main(String[] args) {
		// [9,3,7],[6,3]
		ListNode node3 = new ListNode(7);
		ListNode node2 = new ListNode(3);
		ListNode node1 = new ListNode(9);
		node1.next = node2;
		node2.next = node3;
		
		ListNode node5 = new ListNode(3);
		ListNode node4 = new ListNode(6);
		node4.next = node5;
		BM11_链表相加二 test = new BM11_链表相加二();
		ListNode node = test.addInList01(node1, node4);
		System.out.println(node);
	}
	
	public ListNode addInList (ListNode head1, ListNode head2) {
		if(head1 == null) return head2;
		if(head2 == null) return head1;
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        while (head1 != null) {
			stack1.push(head1);
			head1 = head1.next;
		}
        
        while (head2 != null) {
			stack2.push(head2);
			head2 = head2.next;
		}
        // 创建新的链表头节点
        ListNode newNode = null;
        ListNode head = null;
        //进位符号
        int carry = 0;
        int temp = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
        	int val1 = stack1.isEmpty() ? 0 : stack1.pop().val;
        	int val2 = stack2.isEmpty() ? 0 :  stack2.pop().val;
        	
        	temp = val1 + val2 + carry;
        	carry = temp / 10;
        	temp = temp % 10;
        	newNode = new ListNode(temp);
        	newNode.next = head;
        	head = newNode;
		}
        return head;
    }

	public ListNode addInList01(ListNode head1, ListNode head2) {
		if(head1 == null) return head2;
		if(head2 == null) return head1;
		ListNode node1 = reverse(head1);
		ListNode node2 = reverse(head2);
		
		// 创建新的链表头节点
        ListNode newNode = null;
        ListNode head = null;
        //进位符号
        int carry = 0;
        int temp = 0;
        while (node1 != null || node2!= null) {
        	int val1 = 0;
        	int val2 = 0;
        	if(node1 == null) {
        		val1 = 0;
        	}else {
        		val1 = node1.val;
        		node1 = node1.next;
        	}
        	if(node2 == null) {
        		val2 = 0;
        	}else {
        		val2 = node2.val;
        		node2 = node2.next;
			}
        	
        	temp = val1 + val2 + carry;
        	carry = temp / 10;
        	temp = temp % 10;
        	newNode = new ListNode(temp);
        	newNode.next = head;
        	head = newNode;
		}
        return head;
	}
	
	// 反转链表
    ListNode reverse(ListNode head){
    	if(head == null) return head;
    	ListNode newHead = null;
    	while(head != null) {
    		ListNode temp = head.next;
    		head.next = newHead;
    		newHead = head;
    		head = temp;
    	}
    	return newHead;
    }
}
